package org.hhchat.leetcode.dp;

/**
 * Created by HMH on 2017/4/2.
 */
public class code516 {
    public static class Solution {
        public int longestPalindromeSubseq(String s) {
            int len=s.length();
            int dp[][] = new int[s.length()][s.length()];
            for(int i=0;i<s.length();i++) {
                dp[i][i] = 1;
            }
            for(int strl=2;strl<=len;strl++) {
                for(int start = 0;start<=len-strl;start++) {
                    int end = start + strl - 1;
                    if(s.charAt(start)!=s.charAt(end))
                        dp[start][end] = Math.max(dp[start + 1][end], dp[start][end - 1]);
                    else
                        dp[start][end] = dp[start + 1][end - 1] + 2;
                }
            }
            return dp[0][len - 1];
        }

    }
    public static void main(String[] args){
        System.out.println(new Solution().longestPalindromeSubseq("bbbab"));
    }
}
